package LeetCode._01算法入门.day03双指针;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author 挚爱之夕
 * @date 2022-02-22 - 02 - 22 - 19:35
 * @Description 给定一个数组 nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。
 * 注意：必须在不复制数组的情况下原地对数组进行操作。
 * @Version 1.0
 */
public class _283移动0 {
    static int[] nums = {1, 0, 2, 0, 3};
    //by me : 内存大，速度慢
    @Test
    public void solve(){
        moveZeroes(nums);
        Arrays.stream(nums).forEach(System.out::print);
    }
    //左指针找0，右指针找非0，交换
    public void moveZeroes(int[] nums) {
        int length = nums.length;
        int left = 0;
        int right = 0;
        while(right < length){//left指向0停下，所以用right做结束条件
            while(left < length && nums[left] != 0){//find 0
                left++;
            }
            //从left后面找非零数
            right = left + 1;
            while(right < length && nums[right] == 0){//find 非 0
                right++;
            }
            if(right < length){
                //交换
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                //交换后，当前left指向非0。后移，找下一个
                left++;
            }
        }
    }
    /*官方思路*/
    @Test
    public void solve1(){
        moveZeroes1(nums);
        Arrays.stream(nums).forEach(System.out::print);
    }

    //right指向非0，则交换
    public void moveZeroes1(int[] nums) {
        int n = nums.length, left = 0, right = 0;
        while (right < n) {
            if (nums[right] != 0) {
                if(left != right)   //没遇到0之前，left和right指向同一元素
                    swap(nums, left, right);
                left++;
            }
            right++;
        }
    }

    public void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
    /*取巧的方法*/
    public void moveZeroes2(int[] nums) {
        int current = 0;
        //将非零数依次赋值给数组前几位
        for(int i = 0; i < nums.length; i++){
            if(nums[i] != 0){
                nums[current++] = nums[i];
            }
        }
        //剩下的位置补0
        while(current < nums.length){
            nums[current++] = 0;
        }
    }
}
